package a14_Sort;

/**
 * @Author quan
 * @Description 直接插入排序
 * @Date 2023/4/27 9:38
 */
public class insertSort {
    public static void main(String[] args) {
        int[] arr = {1,56,23,4,12,9,6,8,17};
        insetSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void insetSort(int[] arr){
        int startIndex = 0;
        //先找到有序区间
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i] > arr[i+1]){
                startIndex = i;
                break;
            }
        }
        //有序区间[0,i]
        //无序区间[i+1,n)
        for (int i = startIndex+1; i < arr.length; i++) {
            //i当前无序区间的第一个值，j表示有序区间新增的值，然后每次新增一个值就要往前看不断调整有序区间使之有序。
            for (int j = i; j >= startIndex; j--) {
                if(arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }

    //交换函数
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
